package com.hyper_yang.algorithmRecord.June;

import java.util.Arrays;

// 2025.06.02  分发糖果
public class LeetCode_135 {
    /*
        n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
        你需要按照以下要求，给这些孩子分发糖果：
        每个孩子至少分配到 1 个糖果。
        相邻两个孩子评分更高的孩子会获得更多的糖果。
        请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
     */
    // 方法一: 贪心
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        // 初始化，每个孩子先分 1 个糖果
        Arrays.fill(candies, 1);

        // 从左到右：保证右边比左边评分高时糖果多
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // 从右到左：保证左边比右边评分高时糖果多
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1); // 不取 max时，[1, 3, 2, 2, 1] 思考！！！
            }
        }

        // 统计总糖果数
        int total = 0;
        for (int c : candies) {
            total += c;
        }
        return total;
    }

    public static void main(String[] args) {
        LeetCode_135 solution = new LeetCode_135();
        System.out.println(solution.candy(new int[]{1, 0, 2})); // 5
        System.out.println(solution.candy(new int[]{1, 2, 2})); // 4
    }
}
